/*
 * Copyright (c) 2011 Robert Kirchgessner <rkirchge@gmail.com>
 *                    Carlo Pascoe <carlo.pascoe@gmail.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#pragma once
#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <stdint.h>
#include <sys/queue.h>

#define COORD(X,Y,N) (X*N + Y)

struct vertice 
{
  uint32_t id; /*Vertice ID*/
  uint32_t degree;
  LIST_HEAD(edgelist_head, edge) edges;
  LIST_ENTRY(vertice) next;
};

struct edge 
{
  struct vertice *v; /*Pointer to the referenced vertice*/
  LIST_ENTRY(edge) next; /*Next edge entry*/
};

struct graph
{
  uint32_t size; /*Number of vertices in the graph*/
  uint32_t edges; /*Number of edges in the graph*/
  LIST_HEAD(vertice_list, vertice) vertices; /*Vertices that make up the graph*/
};

/**
 * @brief Initializea new graph with a specified number of vertices
 * @param g Pointer to a graph structure
 */
void graph_init(struct graph *g);

/**
 * @brief Delete all graph related memory allocation
 * @param g Pointer to a graph structure
 */
void graph_cleanup(struct graph *g);

/**
 * @brief Inserts a vertex with a given ID iff it does not already exist.
 * @param g Pointer to a graph structure
 * @param id The id of the node to try to insert.
 * @return Return a pointer to the newly added vertice
 */
struct vertice * graph_insert_vertex(struct graph *g, uint32_t id);

/**
 * @brief Inserts an edge between two nodes with specified ids
 * @param g Pointer to a graph structure
 * @param id0 ID of the first vertex
 * @param id1 ID of the second vertex
 */
void graph_insert_edge(struct graph *g, uint32_t id0, uint32_t id1);

/**
 * @brief Make the adjacency matrix for a graph
 * @param g Pointer to a graph structure
 * @param adj Pointer to a matrix with enough size to store adjacency matrix
 */
void graph_make_adjacency(struct graph *g, uint32_t *adj);

/**
 * @brief Print simple human readable version of the graph
 * @param g Pointer to a graph structure
 */
void graph_print(struct graph *g);

/**
 * @brief Write dotty graph
 * @param fname File to write
 * @param g Pointer to a graph structure
 */
void graph_write_dotty(const char *fname, struct graph *g);

/**
 * Return the degree of a vertice
 */
uint32_t graph_get_degree(struct vertice *v);

/**
 * Check to see if two vertices have an edge (i.e. are adjacent)
 */
uint32_t graph_is_adjacent(struct vertice *v0, struct vertice *v1);

/**
 * Efficiently copies the graph
 */
void graph_copy(struct graph *g0, uint32_t *adj, struct graph *g1);

/**
 * Build a graph from an adjacency matrix
 */
void graph_from_adj(uint32_t *adj, uint32_t size, struct graph *g);

/**
 * Check if a graph is equal
 */
uint32_t graph_isomorphic(struct graph *g0, struct graph *g1);

/**
 * Load graph from file (using edgelist format)
 */
uint32_t graph_from_file(const char *fname, struct graph *g);

#endif /*_GRAPH_H_*/

